In this report, we study the multiparty communication complexity problem ofthe multiparty equality function (MEQ): EQ(x_1,...,x_n) = 1 if x_1=...=x_n, and0 otherwise. The input vector (x_1,...,x_n) is distributed among n>=2 nodes,with x_i known to node i, where x_i is chosen from the set {1,...,M}, for someinteger M>0. Instead of the "number on the forehand" model, we consider a point-to-pointcommunication model (similar to the message passing model), which we believe ismore realistic in networking settings. We assume a synchronous fully connectednetwork of n nodes, the node IDs (identifiers) are common knowledge. We assumethat all point-to-point communication channels/links are private such that whena node transmits, only the designated recipient can receive the message. Theidentity of the sender is known to the recipient. We demonstrate that traditional techniques generalized from two-partycommunication complexity problem are not sufficient to obtain tight boundsunder the point-to-point communication model. We then introduce techniqueswhich significantly reduce the space of protocols to study. These techniquesare used to study some instances of the MEQ problem.
展开▼
